/*
* 1.找到一门掌握人数最多的语言
* 2.找到这个语言中不能相互沟通的好友
* 3.
*/
class Solution {
public:                         //languages[i]:i掌握的语言种类      friendships[i]=(u,v):u,v是朋友
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        unordered_set<int> uncontacts; //存储所有不能相互沟通的好友
        for(auto friends:friendships)  //枚举每个人
        {
            unordered_map<int, int> mp; //当前这对好友是否相互沟通
            bool contact=false;
            for(int lang:languages[friends[0]-1]) mp[lang]=1; //记录这对朋友的第一位掌握的语言 人下标从0开始计算
            for(int lang:languages[friends[1]-1]) {
                if(mp[lang]){ //如果当前这对朋友语言相通
                    contact=true; break;
                }
            }
            if(!contact) { //如果当前语言不通
                uncontacts.insert(friends[0]-1);
                uncontacts.insert(friends[1]-1);
            }
        }
        int maxcnt=0;
        vector<int> cnt(n+1, 0);
        for(auto person:uncontacts) //枚举存在语言不通的朋友
            for(int lang:languages[person]) //累加当前这个人所有会的语言
            {
                cnt[lang]++; maxcnt=max(maxcnt, cnt[lang]);
            }
        return uncontacts.size()-maxcnt; //不会的人-某个掌握人数最多的语言的人数

    }
};